package leo.mystudy.leetcode.dp;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author leo
 * @version 1.0.0
 * @description
 * @create 2022/3/16 10:34
 */
public class LongestSubstring {
    public static void main(String[] args) {
        System.out.println(new LongestSubstring().longestSubstring("aabcabb",
                3));
    }

    public int longestSubstring(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        Set<Character> ltKChar = findLtKChar(s, k);
        if (ltKChar.isEmpty()) {
            return s.length();
        }
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (ltKChar.contains(c)) {
                max = Math.max(max, longestSubstring(s.substring(0, i), k));
                max = Math.max(max, longestSubstring(s.substring(i + 1), k));
                break;
            }
        }
        if (max < k) {
            return 0;
        }
        return max;
    }

    private Set<Character> findLtKChar(String s, int k) {
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            countMap.compute(s.charAt(i), (key, old) -> {
                if (old == null) {
                    return 1;
                } else {
                    return old + 1;
                }
            });
        }
        Set<Character> result = new HashSet<>();
        for (Map.Entry<Character, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() < k) {
                result.add(entry.getKey());
            }
        }
        return result;
    }


//    public int longestSubstring(String s, int k) {
//        int max = 0;
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = s.length(); j > i + max; j--) {
//                String temp = s.substring(i, j);
//                if (isGtK(temp, k)) {
//                    max = temp.length();
//                    break;
//                }
//            }
//        }
//        return max;
//    }
//
//    private boolean isGtK(String s, int k) {
//        System.out.println("deal string:" + s);
//        Map<Character, Integer> countMap = new HashMap<>();
//        for (int i = 0; i < s.length(); i++) {
//            countMap.compute(s.charAt(i), (key, old) -> {
//                if (old == null) {
//                    return 1;
//                } else {
//                    return old + 1;
//                }
//            });
//        }
//        for (Integer value : countMap.values()) {
//            if (value < k) {
//                return false;
//            }
//        }
//        return true;
//    }

}
